package stack;

/**
 * 顺序栈
 *
 * @param <T>
 * @author wt
 */
public class SeqStack<T> implements SStack<T> // 顺序栈类，实现栈接口
{
    private T element[]; // 存储栈数据元素的数组
    private int top; // 栈顶元素下标

    /**
     * 构造容量为size的空栈
     */
    public SeqStack(int size) {
        this.element = (T[]) new Object[Math.abs(size)];
        this.top = -1;
    }

    /**
     * 构造默认容量的空栈
     */
    public SeqStack() {
        this(64);
    }

    /**
     * 判断栈是否空，若空返回true
     */
    public boolean isEmpty() {
        return this.top == -1;
    }

    /**
     * 判断栈满
     */
    public boolean isFull() {
        return top + 1 == element.length;
    }

    /**
     * 元素x入栈，空对象不能入栈
     */
    public void push(T x) {
        if (x == null) { // 空对象不能入栈
            return;
        }

        // 若栈满，则扩充栈容量
        if (this.top == element.length - 1) {
            Object[] temp = this.element;
            // 重新申请一个容量更大的数组
            this.element = (T[]) new Object[temp.length * 2];
            // 复制数组元素，O(n)
            for (int i = 0; i < temp.length; i++) {
                this.element[i] = (T) temp[i];
            }
        }
        this.top++;
        this.element[this.top] = x;
    }

    public int getLength() {
        return top + 1;
    }

    /*
     * 出栈，返回栈顶元素，若栈空返回null
     */
    public T pop() {
        return this.top == -1 ?
                null : (T) this.element[this.top--];
    }

    /*
     * 取栈顶元素，未出栈，若栈空返回null
     */
    public T getTop() {
//        System.out.println("取栈顶元素:");
        return this.top == -1 ? null : (T) this.element[this.top];
    }

    /*
     * 返回栈所有元素的描述字符串，形式为“(,)”，算法同顺序表
     */
    public String toString() {
        System.out.print("当前顺序栈内元素为:");
        String str = "(";
        if (this.top != -1) {
            str += this.element[this.top].toString();
        }
        for (int i = this.top - 1; i >= 0; i--) {
            str += ", " + this.element[i].toString();
        }
        System.out.println(str + ")");
        return str + ") ";
    }
}
